package main.剑指OfferⅠ;

import java.util.Arrays;

public class Day23 {
    public static void main(String[] args) {
        System.out.println("剑指Offer39.数组中出现次数超过一半的数字");
        System.out.println("剑指Offer66.构建乘积数组");
    }
}

class Offer39{
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int result=0,length= nums.length;
        for (int i=0;i<length;){
            if (nums[i]==nums[i+length/2]) {
                result=nums[i];
                break;
            }else {
                int j=i+1;
                while (nums[i]==nums[j]) j++;
                i=j;
            }
        }
        return result;
    }
}

class Offer66{
    public int[] constructArr(int[] a) {
        int length=a.length,forwardMul=1,oppositeMul=1;
        int[] forwardDp=new int[length],oppositeDp=new int[length],result=new int[length];
        for (int i=0;i<length;i++){
            forwardMul*=a[i];
            oppositeMul*=a[length-1-i];
            forwardDp[i]=forwardMul;
            oppositeDp[length-1-i]=oppositeMul;
        }
        for(int i=0;i<length;i++){
            if (i==0) result[i]=oppositeDp[i+1];
            else if (i==length-1) result[i]=forwardDp[i-1];
            else result[i]=forwardDp[i-1]*oppositeDp[i+1];
        }
        return result;
    }
}